Within the fields of computer vision and image processing, a number of techniques have been proposed or suggested for performing image segmentation. Image segmentation techniques typically segment an entire image into distinct regions, such that every pixel in the original image belongs to a connected region in the segmented image. For a general discussion of image segmentation methods, see, for example, N. R. Pal & S. K. Pal, “A Review of Image Segmentation Techniques,” Pattern Recognition, Vol. 26, No. 9, 1277–94 (1993), incorporated by reference herein. Typically, segmentation methods perform global optimization such that each region is maximally homogeneous based on image attributes such as color, texture and brightness and such that region boundaries lie as much as possible along edges. Top down methods that perform global segmentation may be based on a “split and merge” paradigm. Bottom up methods, on the other hand, are typically based on “region growing.” Region growing techniques often involve an initial location in the image, called a seed, where the region growing begins. Conventional segmentation techniques, however, do not rely on initial boundary information provided by the user.
In addition to general image segmentation techniques, a number of techniques have been proposed or suggested for determining a contour or boundary from an image given a set of input points. The pioneer work in this area is based on a variational approach in which a cost function composed of image and contour forces is minimized This work is often referred to as the “active contour” model or more graphically, as “snakes.” The image forces are typically based on gradient information and the contour forces are computed from constraints such as smoothness and elasticity. In the active contour model, the input is a number of fairly accurate points and the desired result is a contour fitted to the image passing near these points. For a more detailed discussion of the active contour model, see, for example, M. Kass et al., “Snakes: Active Contour Models,” IEEE Proc. Int'l Conf. Computer Vision, ICCV87, 259–268 (London 1987); S. C. Zhu & A. Yuille, “Region Competition: Unifying Snakes, Region Growing, and Bayes/MDL for Multiband Image Segmentation,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 18, No. 9, 884–900 (September, 1996) and M. Etoh, “Active Contour Extraction Based on Region Descriptions Obtained from Clustering,” Systems and Computers in Japan, Vol. 25, No. 11, 1111–19 (1993), each incorporated by reference herein. The active contour model approach generally attempts to find a contour, rather than a closed region which best fits the user's input.
In the standard contour model, region information is not used. The resulting curve may follow maximal gradients which lie along different regional boundaries. Secondly, the input and output of the active contour is based upon a fixed number of points. Therefore, the accuracy or resolution of the result, and the associated speed of the computation, is directly dependent on the number of points. As a variational approach, energy values result from integrating along the entire contour; every part of the solution is dependent on the entire configuration. This becomes an expensive procedure that employs matrix computations that are more cumbersome as the complexity of the energy function increases. Another limitation of the active contour method is the use of constraints on the smoothness or elasticity of the curve. The smoothness is assumed to be known a priori. The results of the active contour method depend on the values of the smoothness or elasticity constraints.
The use of simulated annealing as an optimization process in image processing and computer vision is widespread. For example, H. L. Tan et al., “A Cost Minimization Approach to Edge Detection Using Simulated Annealing,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 14, No. 1, 3–18 (January, 1991), incorporated by reference herein, discloses an edge detection method using simulated annealing. Likewise, S. M. Bhandarkar & H. Zhang, “Image Segmentation Using Evolutionary Computation,” IEEE Trans. on Evolutionary Computation, Vol. 3, No. 1, 1–21 (April 1999), incorporated by reference herein, discloses a global image segmentation method using simulated annealing.
These simulated annealing methods, however, do not find a single region based on an input from a user. Rather, they identify more global solutions to edge detection and image segmentation. A. Lundervold & G. Storvik, “Segmentation of Brain Parenchyma and Cerebrospinal Fluid in Multispectral Magnetic Resonance Images,” IEEE Trans. on Medical Imaging, Vol. 14, No. 2, 339–349 (June, 1995), incorporated by reference herein, discloses a methodology to match medical image information to an atlas. In this work, models of specific a priori information are used to solve the task. For example, the number of tissues to identify is known, as well as some of the statistical differences in tissue types. This methodology is applicable only where information regarding the domain is available.
The optimization may also be implemented using a genetic algorithm, as described, for example, in M. Gudmunddsson et al., “Edge Detection in Medical Images Using a Genetic Algorithm,” IEEE Trans. on Medical Imaging, Vol. 17, No. 3, 469–474 (June 1998), incorporated by reference herein. In addition, S. Cagnoni et al., “Interactive Segmentation of Multi-Dimensional Medical Data with Contour-Based Application of Genetic Algorithms,” IEEE (1994), incorporated by reference herein, discloses a genetic approach to semi-automatically segment medical images. These genetic approaches utilize two or more user-supplied two-dimension training samples to segment the region of interest in three-dimensions. One sample is used as seed information and the other samples are used to evaluate the fitness function. The fitness function, however, does not use region information. Rather, the fitness function is based on connectivity, edge similarity and proximity. New edge points are found using a genetically evolving detector. The result of the genetic approaches is a set of points that do not necessarily define a connected boundary. To obtain a connected boundary or boundaries requires a later stage to perform interpolation and contour extraction. For the latter, the genetic approaches propose a differential elastic model.
Global segmentation methods mark every pixel in an image as a member of one of a finite number of different connected regions. Generally, global segmentation methods are fully automatic and do not rely on user input. In some instances of region growing, a seed point (a single location) is specified by the user. In a few cases, users interactively specify contour information but in each of these cases, their final objective differs. In A. Lundervold & G. Storvik, referenced above, the objective is to segment a specific type of medical image based on a model. In S. Cagnoni et al., referenced above, the objective is to use two dimension information to detect edge contours in three dimensions based only on edge information.
Contour or boundary detection methods attempt to find an optimal boundary based on image and user information. Contour or boundary detection methods typically do not use region information and are generally based on the initial information of a fixed set of vertices. In addition, assumptions concerning the smoothness, elasticity, or rigidity of the contour are often an important aspect of these methods. The solution depends on the values of these constraints. When smoothness, elasticity, or rigidity of the contour are not known a priori, or if one or more of these value change along different portions of the boundary, then the wrong solution is found. When a variational approach is applied, the method becomes more costly as the number of points increases.
A need therefore exists for methods and apparatus that identify a region in an image using a set of ordered points, i.e., samples from a continuous contour, to derive a unique connected region. A further need exists for methods and apparatus that identify a region in an image using a set of ordered points to perform single region identification based on both edge and region information. A need exists for methods and apparatus that identify a region in an image by applying simulated annealing techniques to single region detection based on a user input (or prior information) of an initial estimate of the region. A further need exists for methods and apparatus that identify a region in an image by combining proximity to an initial estimate of the region of interest, with a measure of region dissimilarity for evaluating the cost function to be optimized for region identification. Yet another need exists for methods and apparatus that identify a region in an image using a set of configuration changes to be evaluated by an optimization process based on various sized incremental growths of a single region.